package org.lql.algo.codecrush.week008;

import org.lql.algo.common.ListNode;

import java.util.HashSet;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 23:59
 * @description: 面试题 02.01. 移除重复节点 <a href="https://leetcode.cn/problems/remove-duplicate-node-lcci/description/">...</a>
 **/
public class RemoveDuplicateNodes {

	public ListNode removeDuplicateNodes(ListNode head) {
		if (head == null) {
			return null;
		}
		HashSet<Integer> set = new HashSet<>();
		set.add(head.val);
		ListNode cur = head;
		while (cur.next != null) {
			if (set.contains(cur.next.val)) {
				// 重复节点，跳过
				cur.next = cur.next.next;
			} else {
				// 不重复节点，加入集合
				set.add(cur.next.val);
				cur = cur.next;
			}
		}
		return head;
	}

	public ListNode removeDuplicateNodesA(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode cur = head;
		while (cur != null) {
			ListNode prev = cur;
			ListNode p = cur.next;
			while (p != null) {
				if (p.val == cur.val) {
					prev.next = p.next; // 删除重复节点
				} else {
					prev = p;
				}
				p = p.next;
			}
			cur = cur.next;
		}
		return head;
	}

	public static void main(String[] args) {
		RemoveDuplicateNodes removeDuplicateNodes = new RemoveDuplicateNodes();
		ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(2, new ListNode(1))))));
		ListNode listNode = removeDuplicateNodes.removeDuplicateNodesA(head);
		ListNode.printList(listNode);
	}
}
